/**
 * 1. 快 指针，先走 n 步
 * 2. 慢 指针，再一步一步走
 * 3. pre 指针，指向【慢】指针的【前】一个节点
 */

struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
  if (head == NULL || head->next == NULL)
  {
    return NULL;
  }

  struct ListNode *p1 = head;  //慢指针
  struct ListNode *p2 = head;  //快指针
  struct ListNode *pre = NULL; //指向删除节点的前一个节点指针

  // 1. 先让【快指针 p2】先走【n】步
  int i = 0;
  while (i < n)
  {
    p2 = p2->next;
    ++i;
  }

  // 2. 再让【慢指针 p1】、【快指针 p2】同时往后开始走，当 p2 指向 NULL 时结束，pre 记录 p2 上一个节点
  while (p2)
  {
    // pre 不断记录【慢指针】的【前一个】节点
    pre = p1;

    // 快、慢，指针，分别开始往后走
    p1 = p1->next;
    p2 = p2->next;
  }

  // 3、删除 pre->next 节点
  if (pre)
  {
    /**
     * pre 节点存在
     */

    pre->next = p1->next;
    free(p1);
    p1 = NULL;
  }
  else
  {
    /**
     * pre 节点不存在，即删除倒数第n个节点是【头】节点
     */

    head = p1->next;
    free(p1);
    p1 = NULL;
  }

  return head;
}